О чём раздел про онлайн-обучение, кому и зачем его читать?

Во многих случаях обучение ML-модели ― это однократный процесс, после которого она не меняется и только используется для предсказания. А что, если к нам постоянно поступает новая информация и мы должны её учитывать? Тогда модель должна уметь обновляться при поступлении нового объекта или батча объектов. Грубо говоря, этим и занимается онлайн-оптимизация. Можно заметить, что обновление модели на батче объектов проходит и в процессе стохастической оптимизации, ― и это сходство не случайно.

Оказывается, что все известные вам методы стохастической оптимизации первого порядка ― такие как SGD, AdaGrad, Adam, AMSgrad и другие ― являются в первую очередь алгоритмами онлайн-обучения. Чтобы в этом убедиться, достаточно открыть эти статьи и увидеть, для какой задачи выводятся гарантии на сходимость. Постановка задачи онлайн-обучения является одновременно математически простой и очень общей, соединяя три больших темы:

1. «Классическое» онлайн обучение.
2. Стохастическую оптимизацию на фиксированном датасете. Мы покажем, что любой алгоритм онлайн обучения можно переформулировать, как алгоритм стохастической оптимизации; при этом из гарантий на сходимость, полученных для онлайн обучения, автоматически будет следовать сходимость на фиксированном датасете.
3. Adversarial обучение.

Данный текст является в первую очередь систематизирующим. Мы постараемся достичь следующих целей:

1. Подведем единую математическую базу, необходимую для вдумчивого чтения статей по оптимизации. Это будет полезно ML-теоретикам.
2. Покажем, как исторически развивались методы оптимизации, как из одного метода получался другой, какие проблемы они решали и ― главное ― актуальны ли эти проблемы сейчас.
3. Разберём все «именные» методы оптимизации на набор базовых концепций и покажем, как вы можете самостоятельно их сочетать, создавая оптимальный метод для решения своей задачи. Спойлер: базовых концепций намного меньше, чем наименований методов. Эти знания будут полезны ML-инженерам.
4. Пройдемся по относительно нишевым темам, таким как разреженные методы регуляризации $L_1$ и $L_{1/2}$, и рассмотрим наилучшие методы оптимизации для них. Такие методы невозможно получить в стандартной постановке стохастической оптимизации. Эти знания будут полезны ML-инженерам, занимающимся рекомендательными системами.

В параграфе «Введение в онлайн-обучение», которую вы читаете сейчас, вы познакомитесь с общей постановкой задачи онлайн-обучения, а также с семейством алгоритмов Follow the Regularized Leader (FTRL), которое включает в себя все методы первого порядка. Кроме того, вы узнаете, как сводить задачи стохастической оптимизации к задачам онлайн-обучения и увидите, что этот переход позволяет строить более эффективные методы стохастической оптимизации, особенно для разреженных регуляризаторов вроде $L_1$.

В параграфе «Адаптивный FTRL» вы узнаете, как улучшить сходимость алгоритмов стохастической оптимизации с помощью регуляризаторов и каковы гарантии сходимости для регуляризованных задач. Это позволит вывести AdaGrad как наилучший адаптивный метод для онлайн-оптимизации.

В параграфе «Регуляризация в онлайн-обучении» мы снова поговорим о регуляризации, но на этот раз речь пойдёт о регуляризаторах, которые накладывают на решение определённые органичения, например, разреженность. Вы сможете с новой стороны взглянуть на разреживающие свойства $L_1$-регуляризаторов. Кроме того, мы получим не достижимые с помощью обычных SGD/AdaGrad результаты для разреженных $L_1$ и $L_{1/2}$ регуляризаторов.

В параграфе «Стохастическая оптимизация в Deep Learning» мы перейдём к методам оптимизации в глубоких нейросетях. Вас ждёт краткий исторический обзор и мотивация появления двух важных модификаций AdaGrad ― Adam и RMSprop. Мы покажем, что эти методы ломаются вокруг критических точек, и поговорим о том, как починить это и достичь более точной сходимости (этого эффекта можно достичь либо прямой модификацией алгоритмов (AMSgrad и RAdam), либо косвенно с помощью Learning Rate Scheduler'ов).

В конце параграфа мы соберём воедино все рассмотренные концепции и покажем, как можно комбинировать лучшее из разных методов оптимизации в один новый метод.

Оглавление

Часть 1. Введение

• Постановка задачи
• Выпуклая онлайн-оптимизация
• Follow the Leader
• Follow The Regularized Leader (FTRL)
• Линеаризация и вычислительно эффективный FTRL
• Субдифференциал и субградиентные методы

Часть 2. Адаптивные методы оптимизации

• Аддитивные регуляризаторы
• Классы алгоритмов FTRL
• Гарантии сходимости для алгоритмов FTRL
• Построение эффективного адаптивного FTRL
  • $O(1)$ learning rate
  • $O(\frac{1}{\sqrt{t}})$ learning rate
  • Data-Adaptive learning rate.
  • AdaGrad ― оптимальный data-adaptive метод

Часть 3. Продвинутые методы регуляризации

• Идея неразложения регуляризаторов в субградиентную оценку
  • Связь между Composite-Objective FTRL и Proximal Gradient Descent. Lazy vs Greedy представления
• $L_1$-регуляризация
  • Отбор параметров разреженных моделей
  • Linear Incremental $L_1$. Аналог $L_1$ в Greedy методах
  • Global $L_1$. Лучший метод $L_1$ для онлайн обучения
• $L_2$ регуляризация
  • Weight Decay. Decoupled Weight Decay
• Проекция на выпуклое множество $\chi$

Часть 4. Методы оптимизации в Deep Learning

• RMSprop и Adam
  • Мотивация их создания
  • RMSprop
  • Adam
  • Мотивация для bias correction
  • Почему Adam ошибочно считают лучшим методом стохастической оптимизации
• Как сломать адаптивные методы RMSprop и Adam со скользящим средним
• Чиним RMSprop и Adam
  • Метод AMSgrad
    • Реализация без дополнительной памяти
    • Добавление Bias Correction
  • Learning Rate Scheduling
    • Влияние learning rate decay на сходимость
    • Практические рекомендации
    • Learning rate scheduling vs AdaGrad
• SGD vs Adam. Методы AdamW/SGDW. Улучшение методов с помощью проксимального $L_2$
• Momentum
  • Nesterov Momentum
  • Adan

Часть 5. Заключение

• Таблицы формул. Примеры комбинирования идей

Постановка задачи

Литература. Отсюда и далее, пока явно не скажем о переходе на другие источники информации, используется материал из книги Shai Shalev-Shwartz Online Learning and Online
Convex Optimization

Онлайн-обучение ― это процесс предсказания ответов на последовательность вопросов с учётом знания (возможно, неполного) о предыдущих правильных ответах.

Представим себе следующую игру (назовём её игра (1)). На каждом раунде игры $t$ мы:

1. Получаем $x_t$ ― частичную информацию о текущем «вопросе»;
2. Выбираем модель $w_t$, которой будем делать прогноз;
3. Прогнозируем $p_t(w_t, x_t)$;
4. Получаем истинный ответ $y_t$;
5. Получаем обратную связь-лосс $l(p_t, y_t)$. Лоссы обычно имеют семантику функции ошибки: больше ― хуже, меньше ― лучше.

Цель любого алгоритма онлайн обучения ― минимизация суммарной ошибки прогнозов $Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t)$ для любого количества раундов $T$.

Пока рассмотрим интуитивный пример: линейная регрессия (обозначения взяты из параграфа про линейные модели). Пусть у нас уже сыграны раунды $1,\ldots,t-1$ и есть выборка данных $x_1,\ldots,x_{t-1}$ и ответов $y_1,\ldots,y_{t-1}$.

1. Получаем новый $x_t$. В данном случае просто получаем и пока не используем;
2. Выбираем модель $w_t$, которая наилучшим образом объясняет всю предыдущую имеющуюся выборку $x_{1..t}$ (алгоритм обучения можем выбирать любой, какой нам нравится);
3. Прогнозируем $p_t = <w_t, x_t>$;
4. Получаем правильный ответ $y_t$;
5. Считаем loss $(y_t - p_t)^2$;

Действуя таким образом, мы делаем интуитивное предположение, что ответы $y_t$ как-то зависят от наших $x_t$ и что эту зависимость мы можем выучить из предыдущей выборки, улучшив прогноз на новых объектах.

Предположения

Теория онлайн обучения выгодно отличается от классической теории статистического обучения довольно расслабленными и гораздо более простыми (с точки зрения математических формулировок) условиями. Мы не делаем предположений о некой статистической зависимости между $x_t$, $y_t$. Зависимость может быть детерминированной, стохастической или даже adversarial:

1. Детерминированная: в самом начала игры делается выбор детерминированной зависимости $x_t \rightarrow y_t$
2. Стохастическая: $x_t$ может быть реализациями случайной величины, зависящей от $y_t$
3. Adversarial: мы играем против активного противника, который может на каждом раунде игры по своему усмотрению менять зависимость $x_t \rightarrow y_t$ и/или подбирать $l(p_t, y_t)$, имея на руках в том числе текущий ответ $y_t$, не доступный алгоритму онлайн-обучения

Adversarial постановка включает в себя все остальные как частные случаи, так что сразу будем строить теорию для наиболее общего случая.

Поведение алгоритма на шаге T

Начнем с введения метрики качества алгоритма на некотором раунде игры $T$, а затем расширим ее на все раунды игры.

Если у противника нет никаких ограничений, то противник всегда выигрывает. Поскольку $l(p_t, y_t)$ выбирается после нашего прогноза, он может выбрать любую функцию с сколь угодно большим штрафом.

Чтобы такого не случалось, мы предположим, что все ответы на шаге $T$ должны быть сгенерированы некоторым отображением $h^*: X\rightarrow Y, h^* \in H$, где $H$ ― пространство возможных решений, известное и онлайн-алгоритму, и противнику.

С учетом введенного ограничения на поведение противника, введем понятие regret:

$$Regret_T(h) = \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h(x_t), y_t)$$

Regret ― это метрика того, насколько онлайн алгоритм работает хуже, чем некоторая фиксированная модель-бейзлайн h (regret переводится как «сожаление»: насколько мы пожалели о том, что взяли онлайн алгоритм, а не модель h). Поскольку мы работаем в adversarial случае, то логично сравнивать наш онлайн алгоритм с сильнейшим возможным противником, а именно: противник всегда выбирает не «некоторую», а наилучшую модель-бейзлайн $h^* \in H$:

$$maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right]$$

Поведение алгоритма на всей последовательности раундов игры

Вспомним, что вообще-то мы играем игру с бесконечным числом раундов. В таком случае, естественно будет анализировать поведение ряда $maxRegret(T), T \in \mathbb{N}, T \rightarrow \infty$. Здесь хочется еще раз подчеркнуть, в чем заключается adversarial поведение: на каждом шаге t maxRegret будет иметь свою наилучшую модель $h^*_t$ в бейзлайне:

$$maxRegret(\color{#348FEA}{T_1}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*_{\color{#348FEA}{T_1}}(x_t), y_t)$$

$$maxRegret(\color{#E06A27}{T_2}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*_{\color{#E06A27}{T_2}}(x_t), y_t)$$

Качество онлайн алгоритма на протяжении всей игры

Когда мы говорим про adversarial setting и игру с противником, мы хотим не просто как-то минимизировать кумулятивный $Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t)$, но еще и хотим быть не хуже нашего противника. Потребуем, чтобы

$$\lim\limits_{T \rightarrow \infty} \frac{1}{T}maxRegret(T) = 0$$

Такое условие означает, что regret должен расти медленнее чем линейно (в таком случае говорят, что алгоритм имеет сублинейный regret).

Сублинейности бывают разные. Так, $Regret_T$ может быть ограничен сверху рядом с асимптотикой $\sqrt{T}$ или же рядом с асимптотикой $\log{T}$

Асимптотика $\log{T}$, очевидно, приводит к намного лучшей сходимости. Но достичь этого не всегда возможно. Стандартной асимптотикой regret в большинстве используемых на практике алгоритмов является $\sqrt{T}$, для этой асимптотики условия на задачу наименее жесткие. Все рассматриваемые нами ниже алгоритмы будут иметь асимптотику $\sqrt{T}$ и отличаться в основном константами в оценках (но, конечно, отличия в константах при оценке Regret часто приводят к существенно разному поведению на практике). Любые более мощные асимптотики требуют условий, которые крайне редко выполняются в практических задачах

Online to batch conversion

В данном обзоре мы будем анализировать методы, которые гораздо чаще используются для оптимизации в классической постановке: есть фиксированный датасет $(x_i, y_i)_{i=1}^N$, модель $p_w(x)$ с обучаемыми параметрами $w$ и функция потерь $f$, задача ― найти минимум функции

$$\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i)$$

Если представить, что все наши $f(p_w(x_i), y_i)$ ― независимые одинаково распределенные случайные величины, то можно считать, что на самом деле мы оптимизируем

$$\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i) \approx \mathbb{E}_{(x,y)}f(p_w(x), y)$$

Такую постановку задачи часто называть батчевой (англ. batch). Это означает, что мы можем использовать два класса методов оптимизации:

• методы, которые на каждом шаге смотрят сразу на всю выборку (например, градиентный спуск или метод Ньютона);
• методы, которые на каждом шаге смотрят на случайное подмножество данных в надежде, что, итерируясь по таким подмножествам, мы сможем соптимизировать матожидание $\mathbb{E}f(w)$ (например, SGD). Такие методы называют стохастическими.

Существует специальный класс методов анализа сходимости, называемый online to batch conversion. Они позволяют адаптировать алгоритм онлайн-обучения к постановке задачи стохастической оптимизации на фиксированном датасете; при этом оценка на regret транслируется в асимптотику сходимости стохастической оптимизации. Математически строгий вывод этих методов обычно довольно громоздкий и не дарит более глубокого понимания идей в современных стохастических методах, это чисто технические выкладки, поэтому мы здесь ограничимся интуитивным описанием. Строгий вывод можно найти, например, в упомянутой выше книге Shai Shalev-Schwartz.

Процесс стохастической оптимизации на фиксированном датасете можно представить в виде задачи онлайн обучения, если вытянуть все эпохи (проходы по датасетам) в единую последовательность. Мы получим задачу онлайн обучения, в которой $(x_t, y_t)$ сэмплируются из фиксированного множества $(x_1,y_1),\ldots,(x_N,y_N)$. Строго говоря, тут сэмлпирование двухстадийное:

1. Берем исходное множество функций
2. Сэмплируем из него без возвращения, пока множество не станет пустым
3. Как только оно стало пустым ― заново заполняем его

Таким образом, деление на "эпохи" отчетливо видно и в вытянутой последовательности.

Легко видеть, что эта задача является корректной задачей онлайн обучения. Тут мы активно пользуемся тем, что постановка задачи онлайн обучения математически простая и очень общая. Из корректности данной задачи следует, что все алгоритмы онлайн обучения будут иметь на такой последовательности сублинейный regret.

Следующим шагом давайте взглянем на regret в момент смены эпохи. Обозначим за $M$―число эпох, тогда:

$$maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(h^*(x_i), y_i)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right]$$

Из сходимости последовательности следует сходимость любой ее подпоследовательности, а значит, последовательность regret'ов в моменты смены эпох тоже ведет себя сублинейно:

$$\frac{1}{MN}\max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$

$$\max\limits_{h^* \in H}\left[ \frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$

$$\frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \min\limits_{h^* \in H}\left[ \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0$$

Последнее слагаемое уже выглядит практически как постановка задачи стохастической оптимизации на фиксированном датасете! Интуиция на данный момент подсказывает нам, что разрыв между решениями, даваемыми онлайн обучением, и точным решением задачи батч-оптимизации, будет постепенно сокращаться.

В этот момент интуицию можно выключать―остаются только строгие технические выкладки по ссылкам выше.

Выпуклая онлайн-оптимизация

Выпуклая оптимизация играет центральную роль в анализе алгоритмов онлайн-обучения и позволяет получать эффективные алгоритмы. Вот примеры задач, в которых она хорошо работает:

1. Линейная оптимизация;
2. Expert Advice problem;
3. Линейная/логистическая регрессия.

Для задач, возникающих в глубинном обучении, мы поступим согласно рекомендациям ведущих ученых: возьмем теоретически обоснованный алгоритм выпуклой оптимизации, воткнем в нейросеть и помолимся, чтобы он сохранил свои хорошие свойства. С методами первого порядка, как правило, работает (а здесь мы будем рассматривать только такие методы)

Введём в нашу игру предположение о выпуклости, а заодно попробуем сделать вычисления менее громоздкими. Для этого определим упрощённую игру (2):

1. Выбираем параметрическую модель $w_t$;
2. Получаем извне выпуклую функцию потерь $f_t(w)$;
3. Считаем $f_t$ в точке $w_t$ и получаем наш loss $f_t(w_t)$.

Первое упрощение состоит в том, что прогноз $h_t$ и бейзлайн $h^*_t$ мы теперь берём не из абстрактного функционального множества $H$, а из некоторого параметризованного семейства. Говоря «модель $w_t$», мы имеем в виду «модель, заданная параметрами $w_t$». Скажем, для линейной регрессии это может быть вектор весов и bias. Regret будет записываться следующим образом:

$$maxRegret_T = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w_T^*)$$

Второе упрощение в том, что мы не думаем о признаках $x_t$ и таргетах $y_t$. Вся эта информация спрятана в определение функции $f_t(w)$. Например, для линейной регрессии $f_t(w) = (x_t^Tw - y_t)^2$. При этом теперь у нас нет частичной информации о текущем раунде игры перед выбором новой модели $w_t$: ведь мы сначала выбираем $w_t$ и лишь потом получаем $f_t(w)$.

Обратите внимание: если вы попробуете себе представить онлайн алгоритм на практике, то, как правило, частичная информация о функции $f_t(w)$ перед выбором $w_t$ вам доступна. Например, рассмотрим рекомендательную систему с онлайн-дообучаемой ранжирующей моделью:

1. Пользователь пришел, мы сразу пошли в базу данных за его историей покупок и получили признаковое описание (возможно частичное) $x_t$;
2. С учётом этого признакового описания мы выбираем модель $w_t$ и с её помощью оцениваем релевантность товаров этому пользователю;
3. Смотрим, что купил пользователь и купил ли, это даёт нам $f_t(w_t)$.

Тем не менее, в этом параграфе мы будем считать, что частичной информации нет, потому что хотим разрабатывать наиболее общий фреймворк, а не ad-hoc алгоритмы, использующие конкретный вид этой частичной информации. Если даже для какой-то узкой проблемы можно сформулировать специфический алгоритм, учитывающий частичную информацию, с высокой вероятностью он не будет работать значимо лучше стандартного решения. Если знаете контрпримеры ― напишите, добавим сюда для полноты.

Follow the Leader

Предположим, что мы провели $t$ шагов игры (2) и теперь выбираем модель $w_{t+1}$ (как условились, без информации о $f_{t+1}(w)$). Наиболее естественным выбором будет алгоритм, минимизирующий ошибку на всех предыдущих раундах

$$w_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{t}f_s(w)$$

Такой алгоритм называется Follow The Leader (FTL), потому что мы идем вплотную за наилучшим возможным алгоритмом-бейзлайном в regret (лидером), который учитывает ещё и информацию с $(t+1)$-го шага:

$$w*_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{\color{#E06A27}{t+1}}f_s(w)$$

К сожалению, для алгоритма в таком виде есть важные примеры выпуклых задач, когда он не работает. Допустим, наши функции потерь линейны $f_t(w) = g_t^Tw$. Вам может показаться, что линейная функция не особенно похожа на функцию потерь, но, забегая вперед, именно такие функции потерь встретятся дальше при изучении градиентных онлайн-алгоритмов ($g_t = \nabla f_t(w_t)$).

Рассмотрим одномерную задачу $f_t(w) = g_tw_t$, $g_t \in \mathbb{R}$, $w_t \in[-1;1]$. Пусть

$$g_t = \begin{cases} -0.5 & t=1 \\ 1 & t\%2 = 0 \\ -1 & t\%2 = 1 \end{cases}$$

Алгоритм FTL выглядит так:

$$w_{T+1} = arg\min\limits_w\sum\limits_{t=1}^T g_tw = arg\min\limits_w w\Big(\sum\limits_{t=1}^T g_t\Big)$$

Такие осциллирующие суммы коэффициентов будут заставлять FTL выбирать наихудшее возможное решение в каждом раунде. Функция потерь в каждом раунде будет равна $0.5$, а кумулятивная функция потерь примет вид $\sum\limits_{t=1}^T0.5 = 0.5T$. При этом кумулятивная функция потерь константного решения $w^*=0$ будет равна 0. Получаем линейный regret $0.5T$ относительно бейзлайна $w_T^* = w^* = 0$, алгоритм не сходится.

Follow The Regularized Leader

Чтобы стабилизировать алгоритм, мы добавим регуляризаторы, и назовем получившийся алгоритм Follow The Regularized Leader (FTRL):

$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R(w)\Big]$$

Упражнение. Проверьте, что в примере из предыдущего параграфа добавление регуляризатора стабилизирует осцилляцию решения $w$.

Добавка $R(w)$ должна быть выпуклой и неотрицательной. При этом различный выбор $R(w)$ будет приводить к различным алгоритмам и различным оценкам на regret.

Первое, что приходит в голову ― это $L_2$ регуляризатор $R(w) = \vert\vert w\vert\vert_2^2$. Он даёт алгоритм

$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) +\frac{1}{2\lambda}\vert\vert w\vert\vert_2^2\Big]$$

Adaptive FTRL

Следующая идея―сделать регуляризатор зависящим от данных (то есть от $f_t$) и своим на каждом раунде T:

$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R_T(w)\Big]$$

Забегая вперед―все современные градиентные алгоритмы Adam, RMSProp, AdaGrad и т.д. попадают в это семейство data-dependent регуляризаторов и работают значительно эффективнее любых алгоритмов с константными регуляризаторами $R(w)$.

Обратите внимание: регуляризаторы являются частью алгоритма FTRL, они не входят в формулу для regret, которая по-прежнему имеет вид

$$Regret_T(w^*) = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w^*)$$

Таким образом, мы не изменили постановку решаемой нами задачи, изменили лишь метод ее решения.

Обратите внимание: введение регуляризаторов влияет только на онлайн-алгоритм и выбор $w_t$. Бейзлайны $w_T^*$ выбираются как и раньше:

$$w_T^* = arg\min\limits_w \sum\limits_{t=1}^Tf_t(w)$$

Линеаризация и вычислительно эффективный FTRL

Рассмотрим пример с логистической регрессией $f_t(w) = \log(1 + e^{-y_tw_t^Tx_t})$ и константным $L_2$ регуляризатором:

$$\sum\limits_{t=1}^T \log(1 + e^{-y_tw_t^Tx_t}) + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\longrightarrow\min\limits_w$$

Классический пример использования онлайн логистической регрессии ― предсказание CTR в рекламе. Миллионы запросов в секунду => миллионы решений этой оптимизационной задачи в секунду (если разбивать на батчи ― тысячи, но сути это не меняет). Успех онлайн-алгоритма в таких задачах определяется его вычислительной эффективностью, как по памяти, так и по скорости. Увы, с этим у нашего алгоритма не всё так хорошо:

• Скорость: аналитически задача не решается => FAIL
• Память: нужно хранить все предыдущие запросы $x_t$, $t\in{1..T}$ => FAIL

Здесь нам на помощь приходит линеаризация задачи. Если фунции $f_t(w)$ выпуклые (вниз) и гладкие (на негладкие посмотрим позже), то они удовлетворяют основному свойству выпуклых функций

$$f(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t)$$

Разложим все функции $f_t(w)$ в точках $w_t$:

$$f_t(w) \geq f_t(w_t) + [\nabla f(w_t)]^T(w - w_t)$$

$$f_t(w_t) - f_t(w) \leq [\nabla f(w_t)]^T(w - w_t)$$

Просуммируем от 1 до $T$

$$\sum\limits_{t=1}^T \Big(f_t(w_t) - f_t(w)\Big) \leq \sum\limits_{t=1}^T \Big([\nabla f_t(w_t)]^Tw_t - [\nabla f_t(w_t)]^Tw^T\Big)$$

Теперь обозначим $g_t = \nabla f_t(w_t)$ и рассмотрим выпуклую линейную задачу онлайн обучения с функцией потерь $\widetilde{f}_t(w) = g_t^Tw$. Regret для нее выглядит как

$$LinearizedRegret_T(w^*) = \sum\limits_{t=1}^T g_t^Tw_t - \sum\limits_{t=1}^T g_t^Tw^*$$

Неравенство выше позволяет нам оценить regret исходной задачи через regret линеаризованной:

$$Regret_T(w^*) \leq LinearizedRegret_T(w^*)$$

Минимизируя правую часть неравенства, мы, безусловно, будем минимизировать и левую, так что мы можем выбирать $w_t$ алгоритмом, решающим линеаризованную задачу, и получать хорошо сходящийся метод для исходной задачи.

Посмотрим, будет ли линеаризованный алгоритм вычислительно эффективнее. Посмотрим на линеаризацию задачи с data-depedent регуляризатором:

$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla [f_t(w_t)]^Tw + R_T(w)\Big]$$

Линейные задачи имеют аналитическое решение для широкого спектра $R_T(w)$. Собственно, это и есть основное, что нужно помнить на практике ― выбирать регуляризатор так, чтобы эта задача решалась аналитически. Мы рассмотрим простейший случай $R_T(w) = R(w) = \frac{1}{2\eta}\vert\vert w\vert\vert_2^2$:

$$w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla f_t(w_t)^Tw + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\Big]$$

Справа дифференцируемая функция, так что мы можем найти $w_T$, приравняв к нулю градиент:

$$w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = -\eta z_T,$$

где $z_T = \sum\limits_{t=1}^T \nabla f_t(w_t)$ ― это сумма векторов, которую не нужно пересчитывать заново на каждом шаге, а можно инкрементально обновлять. Благодаря этому нам больше не нужно помнить все предыдущие объекты выборки, достаточно хранить лишь некоторую статистику.

Готово, мы построили наш первый вычислительно эффективный алгоритм онлайн обучения! В дальнейшем мы займемся тем, чтобы найти наилучший вычислительно эффективный алгоритм.

Обратите внимание: теперь вы понимете, почему пример с линейной функцией потерь был так важен: линейные функции соответствуют линеаризованному regret. При этом, как мы уже выяснили, без регуляризатора такие линеаризованные задачи нестабильны.

Обратите внимание: если переписать немного формулу для $w_T$, мы получим:

$$w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = w_{T-1} - \eta \nabla f_t(w_t)$$

Таким образом, формулы FTRL c константным регуляризатором эквивалентны формулам обычного стохастического градиентного спуска. Забегая вперед, скажем, что различия в формулах градиентного спуска и FTRL будут только в разделе Composite objective FTRL. В этих отличиях и будет заключаться преимущество FTRL перед привычным SGD.

Обратите внимание: концепции FTRL и gradient descent в литературе часто называют lazy (ленивая) и greedy (жадная) соответственно.

Gradient descent жадный, потому что алгоритм для обновления $w_{t+1}$ использует только текущий $w_t$ и текущий градиент $g_t$. Всё, что было на предыдущих шагах, алгоритм забывает.

FTRL ленивый, потому что алгоритм в явном виде сохраняет всю информацию с начала обучения и рассчитывает $w_{t+1}$, исходя из всей истории $g_1,\ldots,g_t$, и только после этого применяет все регуляризаторы. Подробнее мы расскажем об этом в разделе «Сравнение Composite Objective FTRL-Proximal и Adaptive Gradient Descent».

Субдифференциал и субградиентные методы

Выше мы рассматривали гладкие функции $f_t(w)$. Гладкость ― сильное ограничение, и оно на самом деле необязательно, можно ослабить условие, если использовать субградиенты.

Когда мы переходили от исходной задачи к линеаризованной, мы использовали основное свойство гладких выпуклых функций

$$f(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t), \quad \forall w_t$$

Гладкость обеспечивает существование $\nabla f(w_t)$ для всех $w_t$. Но нам ведь не нужно, чтобы существовал именно градиент функции. Нам достаточно, чтобы существовал какой-то вектор $g_t$, для которого выполнено неравенство

$$f(w) \geq f(w_t) + g^T(w - w_t)$$

И в этом помогают следующие два понятия.

Субдифференциалом функции $f(w)$ в точке $w_t$ называется множество

$$\partial_{w_t} f(w) = \left\{ g_t \mid f(w) \geq f(w_t) + f^T(w - w_t),\forall w\right\}$$

Субградиентом функции $f(w)$ в точке $w_t$ называется любой элемент множества $\partial f(w_t)$.

Потребуем, чтобы для любой точки был непустой субдифференциал, и дело в шляпе, можно вместо $\nabla f_t(w)$ везде подставлять субградиент $g_t$ и обобщить все выкладки выше на негладкий случай.

Примеры. Для гладких функций субдифференциал состоит из одной точки: градиента функции, а субградиент равен градиенту. В качестве примера функции с нетривиальным субградиентом рассмотрим функцию $f(x) = \vert x \vert$, где $x$ ― скаляр. Субградиент в точке $0$ ― это можество

$$\partial_0|x| = \left\{ \lambda\mid |x| \geq \alpha x \right\}$$

Легко видеть, что $\partial_0\vert x\vert$ ― это отрезок $[-1, 1]$.

Замечание. На практике субдифференциал используют не так часто. Оптимизационные задачи с популярными негладкими регуляризаторами $L_1$ решают «в лоб», без перехода к субградиентной оценке, например, с помощью проксимальных методов.

Обратите внимание. В литературе очень часто используется термин Online Mirror Descent. Mirror descent ― это оптимизационная процедура вида

$$w_{t+1} = arg\min\limits_w \left[\vphantom{\frac12}g_t^Tw + \lambda \psi(w) + \vert\vert w-w_t\vert\vert_2^2\right],$$

в которой $\psi$ ― дополнительный негладкий регуляризатор (например, тот же $L_1$), который мы как раз таки не заменяем на субградиентную оценку, а вместо этого оптимизируем всё «в лоб». Заметьте, что эти формулы идентичны формулам Proximal Gradient Descent. Если у нас нет регуляризатора $\psi$, то формулы эквивалентны обычному gradient descent.

Как вы увидите дальше, Mirror Descent ― это частный случай общего фреймворка, который мы описываем.

Субградиентные методы оптимизации.

Почти все градиентные методы оптимизации обобщаются на негладкие функции. Модифицируется необходимое и достаточное условие минимума для выпуклых функций: точка $w^*$ является минимумом, если субдифференциал содержит ноль: $0 \in \partial f(w^*)$. Очевидно, это прямое обобщение условия для гладких функций, где субдифференциал состоит только из градиента функции.